package ArrayList;

import java.util.Arrays;

/**
 * @Classname JZ51数组中的逆序对 @Description TODO @Date 2022/12/8 8:59 @Created by xjl
 */
public class JZ51数组中的逆序对 {
    /**
     * @description 采用的暴力的方式 这样的时间将超出限制
     * @param: nums
     * @date: 2022/12/8 8:59
     * @return: int
     * @author: xjl
     */
    public int reversePairs(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[i]) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * @description 采用阶段性的排序的思想来实现数据的由于 进而可以计算当前的逆序数的个数
     * @param: nums
     * @date: 2022/12/8 10:10
     * @return: int
     * @author: xjl
     */
    public int reversePairs2(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return 0;
        }
        // 拷贝原始数组
        int[] copy = Arrays.copyOf(nums, len);
        int[] temp = new int[len];
        return calculate(copy, 0, len - 1, temp);
    }

    /**
     * @description 计算nums[left……right] 计算逆序对的个数进行排序
     * @param: nums
     * @param: left
     * @param: right
     * @param: temp
     * @date: 2022/12/8 10:19
     * @return: int
     * @author: xjl
     */
    private int calculate(int[] nums, int left, int right, int[] temp) {
        // 表示不能在分解了
        if (left == right) {
            return 0;
        }

        // 计算中间的值
        int mid = (left + right) >> 1;
        int leftcount = calculate(nums, left, mid, temp);
        int rightcount = calculate(nums, mid + 1, right, temp);
        // 当判断到两个子数组已经是有序的 那就直接返回即可。
        if (nums[mid] <= nums[mid + 1]) {
            return leftcount + rightcount;
        }
        // 合并后的结果
        int mergecount = mergeCount(nums, left, mid, right, temp);
        return leftcount + rightcount + mergecount;
    }

    /**
     * @description nums[left, mid]----nums[mid+1,right]是有序
     * @param: nums
     * @param: left
     * @param: rightcount
     * @param: temp
     * @date: 2022/12/8 10:24
     * @return: int
     * @author: xjl
     */
    private int mergeCount(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }
        int i = left;
        int j = mid + 1;
        int count = 0;
        // 三指针来讲数据重新的设置回原来的数组中 就是归并排序的思路
        for (int k = left; k <= right; k++) {
            if (i == mid + 1) {
                nums[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                nums[k] = temp[i];
                i++;
            } else {
                // 只有在 temp[j]小于左边的最小值的时候 才去计算 这个时候的逆序数对的个数才是: mid-i+1;
                nums[k] = temp[j];
                j++;
                count += (mid - i) + 1;
            }
        }
        return count;
    }
}
